snippet spfa "spfa" b
// ========== spfa BEG
namespace spfa {
    using namespace xlx1;
    typedef long long ll;
    ll dis[maxn];
    bool vis[maxn]; //是否在队列内
    void work(int s){
        memset(dis,0x7f,sizeof(dis));
        dis[s] = 0,vis[s] = 1;
        deque<int> q;
        q.push_back(s);
        while( !q.empty()){
            int u = q.front();q.pop_front();
            vis[u] = 0;
            for( int i = head[u]; ~i ;i=e[i].next){
                int v= e[i].v,w = e[i].w;
                if( dis[v] > dis[u] + w){
                    dis[v] = dis[u] + w;
                    if( !vis[v]){
                        vis[v] = 1;
                        if( q.empty()) q.push_back(v);  //SLF 优化
                        else if( dis[v] < dis[q.front()]) q.push_front(v);
                        else q.push_back(v);
                    }
                }
            }
        }
    }
}
// ========== spfa END
endsnippet

snippet spfa_dfs "spfa找图种正负环" b
/*  求负环为什么dis清0？为什dis,ins只要清一次？
 * */
namespace spfa_dfs{
    using namespace xlx1;
    bool ins[maxn]; //在栈内
    int dis[maxn]; // double ,long long 根据题意更改
    bool dfs(int u){ //找负环
        ins[u] = 1;
        for( int i = head[u]; ~i; i = e[i].next){
             int v = e[i].v,w=e[i].w;
             if( dis[v] > dis[u]+w){
                 dis[v] = dis[u]+w;
                 if( ins[v] || dfs(v) ) return true;
             }
        }
        ins[u] = 0;
        return 0;
    }
    bool wk(){
        memset(dis,0,sizeof(dis));
        memset(ins,0,sizeof(ins)); // bool的全局变量可能不全是0
        for(int i=1;i<=n;++i){
            if( dfs(i) ) return 1;
        }
        return 0;
    }
}
endsnippet

snippet dijkstra "优先队列优化的Dijkstra" b
// ========== dijkstra BEG
namespace dijkstra {
    using namespace xlx1;
    typedef long long ll;
    typedef pair<ll,ll> pairI;
    ll dis[maxn]; 
    bool vis[maxn];
    void work(int s){
        priority_queue<pairI, vector<pairI>, greater<pairI> > q;
        memset(dis,0x3f,sizeof(dis));
        /* memset(vis,0,sizeof(vis)); */
        dis[s]=0;
        q.push(make_pair(0,s));
        while(!q.empty()){
            int now=q.top().second;
            q.pop();
            if(vis[now])continue;
            vis[now]=1;
            for(int i=head[now];i!=-1;i=e[i].next){
                if(dis[e[i].v]>dis[now]+e[i].w){
                    dis[e[i].v]=dis[now]+e[i].w;
                    q.push(make_pair(dis[e[i].v],e[i].v));
                }
            }
        }
    }
}
// ========== dijkstra END
endsnippet
